package find;

/**
 * 二分查找
 * 这里的二分查找方法只有数据不重复的情况下才能正常工作
 */
public class SimpleBinarySearch {

    private static int find(int[] arrSrc, int iDest) {
        int iLow = 0;
        int iHigh = arrSrc.length - 1;

        while (iLow <= iHigh) {
            int iMid = iLow + (iHigh - iLow) / 2;
            if (arrSrc[iMid] < iDest) {
                iHigh = iMid - 1;
            } else if (arrSrc[iMid] > iDest) {
                iLow = iMid + 1;
            } else {
                return iMid;
            }
        }

        return  -1;
    }

    private static int findByRecursion(int[] arrSrc, int iLow, int iHigh, int iDest) {
        if (iLow >= iHigh) {
            return -1;
        }

        int iMid = iLow + (iHigh - iLow) / 2;
        if (arrSrc[iMid] < iDest) {
            return findByRecursion(arrSrc, iLow, iMid - 1, iDest);
        } else if (arrSrc[iMid] > iDest){
            return findByRecursion(arrSrc, iMid + 1, iHigh, iDest);
        } else {
            return iMid;
        }
    }

    public static void main(String[] args) {
        int[] arrSrc = new int[] {1,3,5,6,7,8,9,12};

        System.out.println(find(arrSrc, 4));
        System.out.println(findByRecursion(arrSrc, 0, arrSrc.length - 1, 4));

        System.out.println(find(arrSrc, 6));
        System.out.println(findByRecursion(arrSrc, 0, arrSrc.length - 1, 6));
    }

}
